﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Alogrithms
{
    public class QuickUnionUF
    {
        private int[] id;

        public QuickUnionUF(int N)
        {
            id = new int[N];

            for (int i = 0; i < N; i++)
                id[i] = i;
        }
        private int root(int i)
        {
            while (i != id[i])
                i = id[i];
            return i;
        }

        public bool connected(int p, int q)
        {
            return root(p) == root(q);
        }

        public void union(int p, int q)
        {
            int i = root(p);
            int j = root(q);
            id[i] = j;
        }

        public override string ToString()
        {
            return string.Join(" ", id);
        }

        
    }
}
